
Markov={}
Markov.__index = Markov;

function CopyTable(dst, src)
	for i,v in pairs(src) do
		dst[i] = v;
	end
end

function Markov:new(maxstate, maxrank)
	local markov = {}
	setmetatable(markov, Markov);
	markov.rank = 0;
	markov.maxstate = maxstate;
	markov.maxrank = maxrank;
	markov.primary = MarkovItem:new(markov);
	markov.history = {};
	return markov;
end

function Markov:push(result)
	if result > self.maxstate or result == 0 then
		return false;
	end

	table.insert(self.history, result);
	if table.maxn(self.history)>self.maxrank then
		table.remove(self.history,1);
	end

	local tn = table.maxn(self.history);
	local result_chain = {};
	CopyTable(result_chain, self.history);

	for i=1, tn do
		markov.primary:push(result_chain);
		table.remove(result_chain, 1);
	end
	markov.primary:push({});

	return true;
end

function Markov:predict()
	local rc = {};
	local history = {};
	rc.total = 0;
	CopyTable(history, self.history);
	table.remove(history,1);

	for i=1, self.maxstate do
		local result_chain = {};
		CopyTable(result_chain, history);
		table.insert(result_chain, i);
		rc[i] = self.primary:getcount(result_chain);
		rc.total = rc.total+rc[i];
	end

	for i=1, self.maxstate do
		rc[i] = rc[i]/rc.total;
	end

	return rc;
end

MarkovItem={}
MarkovItem.__index = MarkovItem;

function MarkovItem:new(parent)

	local markovitem = {}
	setmetatable(markovitem, MarkovItem);
	markovitem.count = 0;
	markovitem.rank = parent.rank+1;
	markovitem.maxstate = parent.maxstate;
	markovitem.maxrank = parent.maxrank;
	markovitem.son = {};
	return markovitem;

end

function MarkovItem:push(result_chain)

	if table.maxn(result_chain)>0 then
		local state=result_chain[1];
		local rc = {};
		CopyTable(rc, result_chain);
		table.remove(rc,1);

		if self.son[state]==nil then
			self.son[state] = MarkovItem:new(self);
		end

		self.son[state]:push(rc);
	else
		self.count = self.count+1;
	end

end

function MarkovItem:getcount(result_chain)

	if table.maxn(result_chain)>0 then
		local state=result_chain[1];
		local rc = {};
		CopyTable(rc, result_chain);
		table.remove(rc,1);

		if self.son[state]==nil then
			return 0;
		end
		return self.son[state]:getcount(rc);
	else
		return self.count;
	end

end
